Лекция 9. 2 0Управление транзакциями, сериализация транзакций Поддержание механизма транзакций - показатель уровня разви- тости СУБД. Корректное поддержание транзакций одновременно явля- ется основой обеспечения целостности баз данных (и поэтому тран- закции вполне уместны и в однопользовательских персональных СУБД), а также составляют базис изолированности пользователей во многопользовательских системах. Часто эти два аспекта рассматри- ваются по отдельности, но на самом деле они взаимосвязаны, что и будет показано в этой лекции. Заметим, что хотя с точки зрения обеспечения целостности баз данных механизм транзакций следовало бы поддерживать в пер- нональных СУБД, на практике это обычно не выполняется. Поэтому при переходе от персональных к многопользовательским СУБД поль- зователи сталкиваются с необходимостью четкого понимания природы транзакций. Под транзакцией понимается неделимая с точки зрения воз- действия на БД последовательность операторов манипулирования данными (чтения, удаления, вставки, модификации) такая, что либо результаты всех операторов, входящих в транзакцию, отображаются в БД, либо воздействие всех этих операторов полностью отсутству- ет. Лозунг транзакции - "Все или ничего": при завершении тран- закции оператором COMMIT результаты гарантированно фиксируются во внешней памяти (смысл слова commit - "зафиксировать" резуль- таты транзакции); при завершении транзакции оператором ROLLBACK результаты гарантированно отсутствуют во внешней памяти (смысл слова rollback - ликвидировать результаты транзакции). 9.1 Транзакции и целостность баз данных Понятие транзакции имеет непосредственную связь с понятием целостности БД. Очень часто БД может обладать такими ограничени- ями целостности, которые просто невозможно не нарушить, выполняя только один оператор изменения БД. Например, в базе данных СОТ- РУДНИКИ-ОТДЕЛЫ естественным ограничением целостности является совпадения значения атрибута ОТД_РАЗМЕР в кортеже отношения ОТ- ДЕЛЫ, описывающем данный отдел (например, отдел 320), с числом кортежей отношения СОТРУДНИКИ таких, что значение атрибута СОТР_ОТД_НОМЕР равно 320. Как в этом случае принять на работу в отдел 320 нового сторудника? Независимо от того, какая операция будет выполнена первой, вставка нового кортежа в отношение СОТ- РУДНИКИ или модификация существующего кортежа в отношении ОТДЕ- ЛЫ, после выполнения операции база данных окажется в нецелостном состоянии. Поэтому для поддержания подобных ограничений целостности допускается их нарушение внутри транзакции с тем условием, чтобы к моменту завершения транзакции условия целостности были соблю- дены. В системах с развитыми средствами ограничения и контроля целостности каждая транзакция начинается при целостном состоянии БД и должна оставить это состояние целостными после своего за- вершения. Несоблюдение этого условия приводит к тому, что вместо фиксации результатов транзакции происходит ее откат (т.е. вместо оператора COMMIT выполняется оператор ROLLBACK), и БД остается в таком состоянии, в котором находилась к моменту начала транзак- ции, т.е. в целостном состоянии. Если быть немного более точным, различаются два вида огра- ничений целостности: немедленно проверяемые и откладываемые. К немедленно проверяемым ограничениям целостности относятся такие ограничения, проверку которых бессмысленно или даже невозможно откладывать. Примером ограничения, проверку которого откладывать бессмысленно, являются ограничения домена (возраст сотрудника не может превышать 150 лет). Более сложным ограничением, проверку которого невозможно отложить, является следующее: зарплата сот- рудника не может быть увеличена за одну операцию более, чем на 100,000 рублей. Немедленно проверяемые ограничения целостности соответствуют уровню отдельных операторов языкового уровня СУБД. При их нарушениях не производится откат транзакции, а лишь от- вергается соответствующий оператор. Откладываемые ограничения целостности - это ограничения на базу данных, а не на какие-либо отдельные операции. По умолчанию такие ограничения проверяются при конце транзакции, и их наруше- ние вызывает автоматическую замену оператора COMMIT на оператор ROLLBACK. Однако в некоторых системах поддерживается специальный оператор насильственной проверки ограничений целостности внутри транзакции. Если после выполнения такого оператора обнаруживает- ся, что условия целостности не выполнены, пользователь может сам выполнить оператор ROLLBACK или постараться устранить причины нецелостного состояния базы данных внутри транзакции (видимо, это осмысленно только при использовании интерактивного режима работы). И еще одно замечание. С точки зрения внешнего представления в момент завершения транзакции проверяются все откладываемые ог- раничения целостности, определенные в этой базе данных. Однако при реализации стремятся при выполнении транзакции динамически выделить те ограничения целостности, которые действительно могли бы быть нарушены. Например, если при выполнении транзакции над базой данных СОТРУДНИКИ-ОТДЕЛЫ в ней не выполнялись операторы вставки или удаления кортежей из отношения СОТРУДНИКИ, то прове- рять упоминавшееся выше ограничение целостности не требуется (а проверка подобных ограничений вызывает достаточно большую рабо- ту). 9.2 Изолированность пользователей Во многопользовательских системах с одной базой данных од- новременно могут работать несколько пользователей или прикладных программ. Предельной задачей системы является обеспечение изоли- рованности пользователей, т.е. создание достоверной и надежной иллюзии того, что каждый из пользователей работает с БД в оди- ночку. В связи со свойством сохранения целостности БД транзакции являются подходящими единицами изолированности пользователей. Действительно, если с каждым сеансом работы с базой данных ассо- циируется транзакция, то каждый пользователь начинает работу с согласованным состоянием базы данных, т.е. с таким состоянием, в котором база данных могла бы находиться, даже если бы пользова- тель работал с ней в одиночку. При соблюдении обязательного требования поддержания целост- ности базы данных возможны следующие уровни изолированности транзакций: - Первый уровень - отсутствие потерянных изменений. Расс- мотрим следующий сценарий совместного выполнения двух транзак- ций. Транзакция 1 изменяет объект базы данных A. До завершения транзакции 1 транзакция 2 также изменяет объект A. Транзакция 2 завершается оператором ROLLBACK (например, по причине нарушения ограничений целостности). Тогда при повторном чтении объекта A транзакция 1 не видит изменений этого объекта, произведенных ра- нее. Такая ситуация называется ситуацией потерянных изменений. Естественно, она противоречит требованию изолированности пользо- вателей. Чтобы избежать такой ситуации в транзакции 1 требуется, чтобы до завершения транзакции 1 никакая другая транзакция не могла изменять объект A. Отсутствие потерянных изменений являет- ся минимальным требованием к СУБД по части синхронизации парал- лельно выполняемых транзакций. - Второй уровень - отсутствие чтения "грязных данных". Рассмотрим следующий сценарий совместного выполнения транзакций 1 и 2. Транзакция 1 изменяет объект базы данных A. Параллельно с этим транзакция 2 читает объект A. Поскольку операция изменения еще не завершена, транзакция 2 видит несогласованные "грязные" данные (в частности, операция транзакции 1 может быть отвернута при проверке немедленно проверяемого ограничения целостности). Это тоже не соответствует требованию изолированности пользовате- лей (каждый пользователь начинает свою транзакцию при согласо- ванном состоянии базы данных и в праве ожидать видеть согласо- ванные данные). Чтобы избежать ситуации чтения "грязных" данных, до завершения транзакции 1, изменившей объект A, никакая другая транзакция не должна читать объект A (минимальным требованием явлется блокировка чтения объекта A до завершения операции его изменения в транзакции 1). - Третий уровень - отсутствие неповторяющихся чтений. Расс- мторим следующий сценарий. Транзакция 1 читает объект базы дан- ных A. До завершения транзакции 1 транзакция 2 изменяет объект A и успешно завершается оператором COMMIT. Транзакция 1 повторно читает объект A и видит его измененное состояние. Чтобы избежать неповторящихся чтений, до завершения транзакции 1 никакая другая транзакция не должна изменять объект A. В большинстве систем это является максимальным требованием к синхронизации транзакций, хотя, как мы увидим немного позже, отсутствие неповторяющихся чтений еще не гарантирует реальной изолированности пользовате- лей. Заметим, что существует возможность обеспечения разных уровней изолированности для разных транзакций, выполняющихся в одной системе баз данных (в частности, соответствующие операторы предусмотрены в стандарте SQL 2). Как мы уже отмечали, для под- держания целостности достаточен первый уровень. Существует ряд приложений, для которых первого уровня достаточно (например, прикладные или системные статистические утилиты, для которых не- коррректность индивидуальных данных несущественна). При этом удается существенно сократить накладные расходы СУБД и повысить общую эффективность. К более тонким проблемам изолированности транзакций отно- сится так называемая проблема кортежей-"фантомов", вызывающая ситуации, которые также противоречат изолированности пользовате- лей. Рассмотрим следующий сценарий. Транзакция 1 выполняет опе- ратор A выборки кортежей отношения R с условием выборки S (т.е. выбарается часть кортежей отношения R, удовлетворяющих условию S). До завершения транзакции 1 транзакция 2 вставляет в отноше- ние R новый кортеж r, удовлетворяющий условию S, и успешно за- вершается. Транзакция 1 повторно выполняет оператор A, и в ре- зультате появляется кортеж, который отсутствовал при первом вы- полнении оператора. Конечно, такая ситуация противоречит идее изолированности транзакций и может возникнуть даже на третьем уровне изолированности транзакций. Чтобы избежать появления кор- тежей-фантомов, требуется более высокий "логический" уровень синхронизации транзакций. Идеи такой синхронизации (предикатные синхронизационные захваты) известны давно, но в большинстве сис- тем не реализованы. 9.3 Сериализация транзакций Понятно, что для того, чтобы добиться изолированности тран- закций, в СУБД должны использоваться какие-либо методы регулиро- вания совместного выполнения транзакций. План (способ) выполнения набора транзакций называется сери- альным, если результат совместного выполнения транзакций эквива- лентен результату некоторого последовательного выполнения этих же транзакций. Сериализация транзакций - это механизм их выполнения по не- которому сериальному плану. Обеспечение такого механизма являет- ся основной функцией компонента СУБД, ответственного за управле- ние транзакциями. Система, в которой поддерживается сериализация транзакций обеспечивает реальную изолированность пользователей. Основная реализационная проблема состоит в выборе метода сериализации набора транзакций, который не слишком ограничивал бы их параллельность. Приходящим на ум тривиальным решением яв- ляется действительно последовательное выполнение транзакций. Но существуют ситуации, в которых можно выполнять операторы разных транзакций в любом порядке с сохранением сериальности. Примерами могут служить только читающие транзакции, а также транзакции, не конфликтующие по объектам базы данных. Между транзакциями могут существовать следующие виды конф- ликтов: - W-W - транзакция 2 пытается изменять объект, измененный не закончившейся транзакцией 1; - R-W - транзакция 2 пытается изменять объект, прочитанный не закончившейся транзакцией 1; - W-R - транзакция 2 пытается читать объект, измененный не закончившейся транзакцией 1. Практическая сериализация транзакций основывается на учете этих конфликтов. Лекция 10. Методы сериализации транзакций Существуют два базовых подхода к сериализации транзакций, основанный на синхронизационных захватах объектов базы данных и на использовании временных меток. Суть обоих подходов состоит в обнаружении конфликтов транзакций и их устранении. Ниже мы расс- мотрим эти подходы рассматриваются сравнительно подробно. Предварительно заметим, что для каждого из подходов имеются две разновидности - пессимистическая и оптимистическая. При при- менении пессимистических методов, ориентированных на ситуации, когда конфликты возникают часто, конфликты распознаются и разре- шаются немедленно при их возникновении. Оптимистические методы основываются на том, что результаты всех операций модификации базы данных сохраняются в рабочей памяти транзакций. Реальная модификация базы данных производится только на стадии фиксации транзакции. Тогда же проверяется, не возникают ли конфликты с другими транзакциями. Далее мы ограничимся рассмотрением более распространенных пессимистических разновидностей методов сериализации транзак- ций. Пессимистические методы сравнительно просто транформиру- ются в свои оптимистические варианты. 10.1 Синхронизационные захваты Наиболее распространенным в централизованных СУБД (вклю- чающих системы, основанные на архитектуре "клиент-сервер") яв- ляется подход, основанный на соблюдении двухфазного протокола синхронизационных захватов объектов БД. В общих чертах прото- кол состоит в том, что перед выполнении любой операции в тран- закции T над объектом базы данных r от имени транзакции T зап- рашивается синхронизационный захват объекта r в соответствую- щем режиме (в зависимости от вида операции). Основные режимы синхронизационных захватов являются: - совместный режим - S (Shared), означающий разделяемый захват объекта и требуемый для выполнения операции чтения объ- екта; - монопольный режим - X (eXclusive), означающий монополь- ный захват объекта и требуемый для выполнения операций занесе- ния, удаления и модификации. Захваты объектов несколькими транзакциями по чтению сов- местимы, т.е. нескольким транзакциям допускается читать один и тот же объект, захват объекта одной транзакцией по чтению не совместим с захватом другой транзакцией того же объекта по за- писи, и захваты одного объекта разными транзакциями по записи не совместимы. Правила совместимости захватов одного объекта разными транзакциями изображены на следующей таблице: ------T-----¬ ¦ X ¦ S ¦ ------+-----+-----+ ¦ - ¦ да ¦ да ¦ +-----+-----+-----+ ¦ X ¦ нет ¦ нет ¦ +-----+-----+-----+ ¦ S ¦ нет ¦ да ¦ L-----+-----+------ В первом столбце приведены возможные состояния объекта с точки зрения синхронизационных захватов. При этом "-" соот- ветствует состоянию объекта, для которого не установлен ника- кой захват. Транзакция, запросившая синхронизационный захват объекта БД, уже захваченный другой транзакцией в несовместимом режиме, блокируется до тех пор, пока захват с этого объекта не будет снят. Заметим, что слово "нет" в нашей таблице соответствует описанным ранее возможным случаям конфликтов транзакций по доступу к объектам базы данных (WW, RW, WR). Совместимость S-захватов соответствует тому, что конфликт RR не существует. Для обеспечения сериализации транзакций (третьего уровня изолированности) синхронизационные захваты объектов, произве- денные по инициативе транзакции, можно снимать только при ее завершении. Это требование порождает двухфазный протокол синх- ронизационных захватов - 2PL. В соответствии с этим протоколом выполнение транзакции разбивается на две фазы: - первая фаза транзакции - накопление захватов; - вторая фаза (фиксация или откат) - освобождение захва- тов. Достаточно легко убедиться, что при соблюдении двухфазно- го протокола синхронизационных захватов действительно обеспе- чивается сериализация транзакций на третьем уровне изолирован- ности. Основная проблема состоит в том, что следует считать объектом для синхронизационного захвата? В контексте реляционных баз данных возможны следующие альтернативы: - файл - физический (с точки зрения базы данных) объект, область хранения нескольких отношений и, возможно, индексов; - отношение - логический объект, соответствующий множест- ву кортежей данного отношения; - страница данных - физический объект, хранящий кортежи одного или нескольких отношений, индексную или служебную ин- формацию; - кортеж - элементарный физический объект базы данных. На самом деле, когда мы говорим про операции над объекта- ми базы данных, то любая операция над кортежем, фактически, является и операцией над страницей, в которой этот кортеж хра- нится, и над соответствующим отношением, и над файлом, содер- жащем отношение. Поэтому действительно имеется выбор уровня объекта захвата. Понятно, что чем крупнее объект синхронизационного захва- та (неважно, какой природы этот объект - логический или физи- ческий), тем меньше синхронизационных захватов будет поддержи- ваться в системе, и на это, соответственно, будут тратиться меньшие накладные расходы. Более того, если выбрать в качестве уровня объектов для захватов файл или отношение, то будет ре- шена даже проблема фантомов (если это не ясно сразу, посмотри- те еще раз на формулировку проблемы фантомов и определение двухфазного протокола захватов). Но вся беда в том, что при использовании для захватов крупных объектов возрастает вероятность конфликтов транзакций и тем самым уменьшается допускаемая степень их параллельного выполнения. Фактически, при укрупнении объекта синхронизацион- ного захвата мы умышленно огрубляем ситуацию и видим конфликты в тех ситуациях, когда на самом деле конфликтов нет. Разработчики многих систем начинали с использования стра- ничных захватов, полагая это некоторым компромиссом между стремлениями сократить накладные расходы и сохранить достуточ- но высокий уровень параллельности транзакций. Но это не очень хороший выбор. Мы не будем останавливаться на деталях, но за- метим, что использование страничных захватов в двухфазном про- токоле иногда вызывает очень неприятные синхронизационные проблемы, усложняющие организацию СУБД. В большинстве совре- менных систем используются покортежные синхронизационные зах- ваты. Но при этом возникает очередной вопрос. Если единицей захвата является кортеж, то какие синхронизационные захваты потребуются при выполнении таких операций как уничтожение от- ношения? Было бы довольно нелепо перед выполнением такой опе- рации потребовать захвата всех существующих кортежей отноше- ния. Кроме того, это не предотвратило бы возможности парал- лельной вставки в другой транзакции нового кортежа в уничтожа- емое отношение. 10.1.1 Гранилированные синхронизационные захваты Подобные рассуждения привели к разработки аппарата грану- лированных синхронизационных захватов. При применении этого подхода синхронизационные захваты могут запрашиваться по отно- шению к объектам разного уровня: файлам, отношениям и корте- жам. Требуемый уровень объекта определяется тем, какая опера- ция выполняется (например, для выполнения операции уничтожения отношения объектом синхронизационного захвата должно быть все отношение, а для выполнения операции удаления кортежа - этот кортеж). Объект любого уровня может быть захвачен в режиме S или X. Теперь наиболее важное отличие, на котором, собственно, держится соответствие захватов разного уровня. Вводится специ- альные протокол гранулированных захватов и новые типы захва- тов: перед захватом объекта в режиме S или X соответствующий объект более верхнего уровня должен быть захвачен в режиме IS, IX или SIX. Что же из себя представляют эти режимы захватов? IS (Intented for Shared lock) по отношению к некоторому составному объекту O означает намерение захватить некоторый входящий в O объект в совместном режиме. Например, при намере- нии читать кортежи из отношения R это отношение должно быть захвачено в режиме IS (а до этого в таком же режиме должен быть захвачен файл). IX (Intented for eXclusive lock) по отношению к некоторо- му составному объекту O означает намерение захватить некоторый входящий в O объект в монопольном режиме. Например, при наме- рении удалять кортежи из отношения R это отношение должно быть захвачено в режиме IX (а до этого в таком же режиме должен быть захвачен файл). SIX (Shared, Intented for eXclusive lock) по отношению к некоторому составному объекту O означает совместный захват всего этого объекта с намерением впоследствии захватывать ка- кие-либо входящие в него объекты в монопольном режиме. Напри- мер, если выполняется длинная операция просмотра отношения с возможностью удаления некоторых просматриваемых кортежей, то экономичнее всего захватить это отношение в режиме SIX (а до этого захватить файл в режиме IS). Довольно трудно описать словами все возможные ситуации. Мы ограничимся приведением полной таблицы совестимости захва- тов, анализируя которую можно выявить все случаи: ------T-----T-----T-----T-----¬ ¦ X ¦ S ¦ IX ¦ IS ¦ SIX ¦ ------+-----+-----+-----+-----+-----+ ¦ - ¦ да ¦ да ¦ да ¦ да ¦ да ¦ +-----+-----+-----+-----+-----+-----+ ¦ X ¦ нет ¦ нет ¦ нет ¦ нет ¦ нет ¦ +-----+-----+-----+-----+-----+-----+ ¦ S ¦ нет ¦ да ¦ нет ¦ да ¦ нет ¦ +-----+-----+-----+-----+-----+-----+ ¦ IX ¦ нет ¦ нет ¦ да ¦ да ¦ нет ¦ +-----+-----+-----+-----+-----+-----+ ¦ IS ¦ нет ¦ да ¦ да ¦ да ¦ да ¦ +-----+-----+-----+-----+-----+-----+ ¦ SIX ¦ нет ¦ нет ¦ нет ¦ да ¦ нет ¦ L-----+-----+-----+-----+-----+------ 10.1.2 Предикатные синхронизационные захваты Несмотря на привлекательность метода гранулированных синхронизационных захватов, следует отметить что он не решает проблему фантомов (если, конечно, не ограничиться использова- нием захватов отношений в режимах S и X). Давно известно, что для решения этой проблемы необходимо перейти от захватов инди- видуальных объектов базы данных, к захвату условий (предика- тов), которым удовлетворяют эти объекты. Проблема фантомов не возникает при использовании для синхронизации уровня отноше- ний именно потому, что отношение как логический объект представляет собой неявное условие для входящих в него корте- жей. Захват отношения - это простой и частный случай предикат- ного захвата. Поскольку любая операция над реляционной базой данных за- дается некоторым условием (т.е. в ней указывается не конкрет- ный набор объектов базы данных, над которыми нужно выполнить операцию, а условие, которому должны удовлетворять объекты этого набора), идеальным выбором было бы требовать синхрониза- ционный захват в режиме S или X именно этого условия. Но если посмотреть на общий вид условий, допускаемых, например, в язы- ке SQL, то становится абсолютно непонятно, как определить сов- местимость двух предикатных захватов. Ясно, что без этого использовать предикатные захваты для синхронизации транзакций невозможно, а в общей форме проблема неразрешима. К счастью, эта проблема сравнительно легко решается для случая простых условий решается. Будем называть простым усло- вием конъюнкцию простых предикатов, имеющих вид имя-атрибута { = > < } значение. В типичных СУБД, поддерживающих двухуровневую организацию (языковой уровень и уровень управления внешней памяти), в ин- терфейсе подсистем управления памятью (которая обычно заведует и сериализацией транзакций) допускаются только простые усло- вия. Подсистема языкого уровня производит компиляцию исходного оператора со сложным условием в последовательность обращений к ядру СУБД, в каждом из которых содержатся только простые усло- вия. Следовательно, в случае типовой организации реляционной СУБД простые условия можно использовать как основу предикатных захватов. Для простых условий совместимость предикатных захватов легко определяется на основе следующей геометрической интерп- ретации. Пусть R отношение с атрибутами a1, a2, ..., an, а m1, m2, ..., mn - множества допустимых значений a1, a2, ..., an соответственно (все эти множества - конечные). Тогда можно со- поставить R конечное n-мерное пространство возможных значений кортежей R. Любое простое условие "вырезает" m-мерный прямоу- гольник в этом пространстве (m <= n). Тогда S-X, X-S, X-X предикатные захваты от разных тран- закций совместимы, если соответствующие прямоугольники не пе- ресекаются. Это иллюстрируется следующим примером, показывающим, что в каких бы режимах не требовала транзакция 1 захвата условия (1<=a<=4) & (b=5), а транзакция 2 - условия (1<=a<=5) & (1<=b<=3), эти захваты всегда совместимы. Пример: (n = 2) b + ¦ (1<=a<=4) & (b=5) 5+ +-----------------+ ¦ 4+ ¦ 3+ ------------------------¬ ¦ ¦ (1<=a<=5) & ¦ 2+ ¦ (1<=b<=3) ¦ ¦ ¦ ¦ 1+ L------------------------ ¦ L-----+-----+-----+-----+-----+ 1 2 3 4 5 a Заметим, что предикатные захваты простых условий описыва- ются таблицами, немногим отличающимися от таблиц традиционных синхронизаторов. 10.1.3 Тупики, распознавание и разрушение Одним из наиболее чувствительных недостатков метода сери- ализации транзакций на основе синхронизационных захватов явля- ется возможность возникновение тупиков (deadlocks) между тран- закциями. Тупики возможны при применении любого из рассмотрен- ных нами вариантов. Вот простой пример возникновения тупика между транзакция- ми T1 и T2: - транзакции T1 и T2 установили монопольные захваты объ- ектов r1 и r2 соответственно; - после этого T1 требуется совместный захват r2, а T2 - совместный захват r1; - ни одна из транзакций не может продолжаться, следова- тельно, монопольные захваты не будут сняты, а совместные - не будут удовлетворены. Поскольку тупики возможны, и никакого естественного выхо- да из тупиковой ситуации не существует, то эти ситуации необ- ходимо обнаруживать и искусственно устранять. Основой обнаружения тупиковых ситуаций является построе- ние (или постоянное поддержание) графа ожидания транзакций. Граф ожидания транзакций - это ориентированный двудольный граф, в котором существует два типа вершин - вершины, соот- ветствующие транзакциям, и вершины, соответствующие объектам захвата. В этом графе существует дуга, ведущая из верши- ны-транзакции к вершине-объекту, если для этой транзакции су- ществует удовлетворенный захват объекта. В графе существует дуга из вершины-объекту к вершине-транзакции, если транзакция ожидает удовлетворения захвата объекта. Легко показать, что в системе существует ситуация тупика, если в графе ожидания транзакций имеется хотя бы один цикл. Для распознавание тупика периодически производится пост- роение графа ожидания транзакций (как уже отмечалось, иногда граф ожидания поддерживается постоянно), и в этом графе ищутся циклы. Традиционной техникой (для которой существует множество разновидностей) нахождения циклов в ориентированном графе яв- ляется редукция графа. Не вдаваясь в детали, редукция состоит в том, что прежде всего из графа ожидания удаляются все дуги, исходящие из вер- шин-транзакций, в которые не входят дуги из вершин-объектов. (Это как бы соответствует той ситуации, что транзакции, не ожидающие удовлетворения захватов, успешно завершились и осво- бодили захваты). Для тех вершин-объектов, для которых не оста- лось входящих дуг, но существуют исходящие, ориентация исходя- щих дуг изменяется на противоположную (это моделирует удовлет- ворение захватов). После этого снова срабатывает первый шаг и так до тех пор, пока на первом шаге не прекратится удаление дуг. Если в графе остались дуги, то они обязательно образуют цикл. Предположим, что нам удалось найти цикл в графе ожидания транзакций. Что делать теперь? Нужно каким-то образом обеспе- чить возможность продолжения работы хотя бы для части транзак- ций, попавших в тупик. Разрушение тупика начинается с выбора в цикле транзакций так называемой транзакции-жертвы, т.е. тран- закции, которой решено пожертвовать, чтобы обеспечить возмож- ность продолжения работы других транзакций. Грубо говоря, критерием выбора является стоимость тран- закции; жертвой выбирается самая дешевая транзакция. Стоимость транзакции определяется на основе многофакторная оценка, в ко- торую с разными весами входят время выполнения, число накоп- ленных захватов, приоритет. После выбора транзакции-жертвы выполняется откат этой транзакции, который может носить полный или частичный харак- тер. При этом, естественно, освобождаются захваты и может быть продолжено выполнение других транзакций. Естественно, такое насильственное устранение тупиковых ситуаций является нарушением принципа изолированности пользо- вателей, которого невозможно избежать. Заметим, что в централизованных системах стоимость пост- роения графа ожидания сравнительно невелика, но она становится слишком большой в по-настоящему распределенных СУБД, в которых транзакции могут выполняться в разных узлах сети. Поэтому в таких системах обычно используются другие методы сериализации транзакций. Еще одно замечание. Чтобы минимизировать число конфликтов между транзакциями, в некоторых СУБД (например, в Oracle) используется следующее развитие подхода. Монопольный захват объекта блокирует только изменяющие транзакции. После выполне- нии операции модификации предыдущая версия объекта остается доступной для чтения в других транзакциях. Кратковременная блокировка чтения требуется только на период фиксации изменяю- щей транзакции, когда обновленные объекты становятся текущими. 10.2 Метод временных меток Альтернативный метод сериализации транзакций, хорошо ра- ботающий в условиях редких конфликтов транзакций и не требую- щий построения графа ожидания транзакций. основан на использо- вании временных меток. Основная идея метода (у которого существует множество разновидностей) состоит в следующем: если транзакция T1 нача- лась раньше транзакции T2, то система обеспечивает такой режим выполнения, как если бы T1 была целиком выполнена до начала T2. Для этого каждой транзакции T предписывается временная метка t, соответствующая времени начала T. При выполнении опе- рации над объектом r транзакция T помечает его своей временной меткой и типом операции (чтение или изменение). Перед выполнением операции над объектом r транзакция T1 выполняет следующие действия: - Проверяет, не закончилась ли транзакция T, пометившая этот объект. Если T закончилась, T1 помечает объект r и выпол- няет свою операцию. - Если транзакция T не завершилась, то T1 проверяет конф- ликтность операций. Если операции неконфликтны, при объекте r остается или проставляется временная метка с меньшим значени- ем, и транзакция T1 выполняет свою операцию. - Если операции T1 и T конфликтуют, то если t(T) > t(T1) (т.е. транзакция T является более "молодой", чем T), произво- дится откат T и T1 продолжает работу. - Если же t(T) < t(T1) (T "старше" T1), то T1 получает новую временную метку и начинается заново. К недостаткам метода временных меток относятся потенци- ально более частые откаты транзакций, чем в случае использова- ния синхронизационных захватов. Это связано с тем, что конф- ликтность транзакций определяеся более грубо. Кроме того, в распределенных системах не очень просто вырабатывать глобаль- ные временные метки с отношением полного порядка (это отдель- ная большая наука). Но в распределенных системах эти недостатки окупаются тем, что не нужно распознавать тупики, а как мы уже отмечали, построение графа ожидания в распределенных системах стоит очень дорого.